1211. Бесконечная последовательность

Определим бесконечную последовательность А следующим образом:

A₀ = 1,

A_i = A_[i/p] + A_[i/q] , i ³ 1

По заданным n, p, q необходимо вычислить A_n.

Вход. Три целых числа n, p, q (0 £ n £ 10¹², 2 £ p, q £ 10⁹).

Выход. Значение A_n.

Пример входа 1	Пример выхода 1
0 2 3	1
Пример входа 2	Пример выхода 2
10000000 3 3	32768

РЕШЕНИЕ

структуры данных – map, рекурсия

Анализ алгоритма

Вычислить все значения A_i (i = 0, 1, …, n) последовательности невозможно при помощи массива из-за ограничения n £ 10¹². Для запоминания результатов будем использовать структуру map: значение A_i будем хранить в m[i]. Находим значение A_n, запоминая промежуточные результаты.

Реализация алгоритма

Для хранения значений A_i объявим переменную m.

map<long long,long long> m;

Функция calc возвращает значение m[n].

long long calc(long long n, int p, int q)

{

if (n == 0) return 1;

if (m.count(n) > 0) return m[n];

return m[n] = calc(n/p,p,q) + calc(n/q,p,q);

}

Основная часть программы. Читаем входные данные. Вычисляем и выводим ответ.

scanf("%lld %lld %lld",&n,&p,&q);

res = calc(n,p,q);

printf("%lld\n",res);

Java реализация

import java.util.*;

public class Main

{

static Map<Long, Long> m = new HashMap<Long, Long>();

public static long calc(long n, long p, long q)

{

if (m.containsKey(n)) return m.get(n);

if (n == 0) return 1;

long res = calc(n/p,p,q) + calc(n/q,p,q);

m.put(n,res);

return res;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong(),

p = con.nextLong(),

q = con.nextLong();

System.out.println(calc(n,p,q));

}

}